package com.cy.linklist;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;

/**
 * @Author: chenyun
 * @Date: 2021/09/17/17:49
 * @Description:
 */

//21. 合并两个有序链表
//输入：l1 = [1,2,4], l2 = [1,3,4]
//输出：[1,1,2,3,4,4]
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
public class Demo21 {

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode tem = new ListNode(0);
        ListNode head = tem;
        TreeMap map = new TreeMap<Integer,ListNode>();
        while (l1 != null){
            map.put(Integer.valueOf(l1.val),l1);
            l1 = l1.next;
        }
        while (l2 != null){
            map.put(Integer.valueOf(l2.val),l2);
            l2 = l2.next;
        }
        Set keys = map.keySet();
        Iterator it = keys.iterator();
        while (it.hasNext()) {
            int key = (int) it.next();
            ListNode node = (ListNode) map.get(key);
            tem.next = node;
            tem = node;
        }

        return head;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = null;

        ListNode listNodel1 = new ListNode(1);
        ListNode listNodel2 = new ListNode(5);
        ListNode listNodel3 = new ListNode(8);
        listNodel1.next = listNodel2;
        listNodel2.next = listNodel3;
        listNodel3.next = null;
        ListNode mergeTwoLists = mergeTwoLists(listNode1, listNodel1);
        while (mergeTwoLists != null){
            System.out.println(mergeTwoLists.val);
        }

    }


}
